W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem [email protected].
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, zapraszamy na serwery Discord. Są one moderowane przez społeczność, ale członkowie zespołu technicznego też są tam aktywni.
Bytetel Company decided to improve computers they produce. They want to replace assembler programs with special systems called assembler circuits. Assembler programs consist solely of assignments. Each assignment is determined by four elements:
We assume that there are at most registers. They are represented by small letters of English alphabet. There are at most elementary operations and they are represented by capital letters A, B, C, D.
An assembler circuit has:
There are gates inside a circuit. Each gate has two inputs and one output. The gate performs an elementary operation on data delivered on its inputs and passes the result to its output. Inputs of gates and outputs of the whole circuit are connected to outputs of other gates or inputs of the circuit. Outputs of gates and inputs of the circuit can be connected to many inputs of other gates or outputs of the circuit. Connections among gates cannot form cycles.
An assembler circuit is equivalent to an assembler program if for any initial state of registers the final state of registers produced by the program and the circuit are the same.
Write a program that:
In the first line of the standard input there is one integer (), which is the number of instructions in the program.
In the following lines there are descriptions of consecutive instructions in the program. Each description is a four-letter word beginning with an elementary operation symbol: A, B, C or D. The second and the third letter (which are small letters of English alphabet) are names of registers, in which data are placed. The fourth letter is a name of a register, in which the result should be placed.
In the first and only line of the standard output there should be written one integer, which is the minimal number of gates in an assembler circuit equivalent to the given program.
For the input data:
8 Afbc Bfbd Cddd Bcbc Afcc Afbf Cfbb Dfdb
the correct result is:
6
A circuit equivalent to the given program is shown in the figure.
Task author: Marcin Kubica.